home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / edit / mg2a_src.zip / REGEX.C < prev    next >
C/C++ Source or Header  |  1988-08-23  |  45KB  |  1,595 lines
  1. /* Imagine Generic gnuemacs copyright notice here */
  2.  
  3. /* modified by Robert Larson to make fewer assumptions about the compiler */
  4. /* (Making it useful to mg) (#if not supported by osk, enum not supported by many) */
  5.  
  6. /* To test, compile with -Dtest.
  7.  This Dtestable feature turns this into a self-contained program
  8.  which reads a pattern, describes how it compiles,
  9.  then reads a string and searches for it.  */
  10.  
  11.  
  12. #ifdef REGEX
  13. #include    "def.h"        /* defines VOID etc. for mg */
  14.  
  15. #ifdef emacs
  16.  
  17. /* The `emacs' switch turns on certain special matching commands
  18.  that make sense only in emacs. */
  19.  
  20. #include "config.h"
  21. #include "lisp.h"
  22. #include "buffer.h"
  23. #include "syntax.h"
  24.  
  25. #else  /* not emacs */
  26.  
  27. /*
  28.  * Define the syntax stuff, so we can do the \<...\> things.
  29.  */
  30.  
  31. #ifndef Sword /* must be non-zero in some of the tests below... */
  32. #define Sword 1
  33. #endif
  34.  
  35. #define SYNTAX(c) re_syntax_table[c]
  36.  
  37. #ifdef SYNTAX_TABLE
  38.  
  39. char *re_syntax_table;
  40.  
  41. #else
  42.  
  43. static char re_syntax_table[256];
  44.  
  45. static VOID
  46. init_syntax_once ()
  47. {
  48.    register int c;
  49.    static int done = 0;
  50.  
  51.    if (done)
  52.      return;
  53.  
  54.    bzero (re_syntax_table, sizeof re_syntax_table);
  55.  
  56.    for (c = 'a'; c <= 'z'; c++)
  57.      re_syntax_table[c] = Sword;
  58.  
  59.    for (c = 'A'; c <= 'Z'; c++)
  60.      re_syntax_table[c] = Sword;
  61.  
  62.    for (c = '0'; c <= '9'; c++)
  63.      re_syntax_table[c] = Sword;
  64.  
  65.    done = 1;
  66. }
  67.  
  68. #endif /* SYNTAX_TABLE */
  69. #endif /* not emacs */
  70.  
  71. #include "regex.h"
  72.  
  73. /* Number of failure points to allocate space for initially,
  74.  when matching.     If this number is exceeded, more space is allocated,
  75.  so it is not a hard limit.  */
  76.  
  77. #ifndef NFAILURES
  78. #define NFAILURES 80
  79. #endif NFAILURES
  80.  
  81. /* width of a byte in bits */
  82.  
  83. #define BYTEWIDTH 8
  84.  
  85. /* These are the command codes that appear in compiled regular expressions, one per byte.
  86.   Some command codes are followed by argument bytes.
  87.   A command code can specify any interpretation whatever for its arguments.
  88.   Zero-bytes may appear in the compiled regular expression. */
  89.  
  90. typedef char regexpcode;
  91. #define unused 0
  92. #define exactn 1    /* followed by one byte giving n, and then by n literal bytes */
  93. #define begline 2    /* fails unless at beginning of line */
  94. #define endline 3    /* fails unless at end of line */
  95. #define jump 4        /* followed by two bytes giving relative address to jump to */
  96. #define on_failure_jump 5 /* followed by two bytes giving relative address of place */
  97.             /* to resume at in case of failure. */
  98. #define finalize_jump 6 /* Throw away latest failure point and then jump to address. */
  99. #define maybe_finalize_jump 7 /* Like jump but finalize if safe to do so. */
  100.             /*  This is used to jump back to the beginning
  101.                 of a repeat.  If the command that follows
  102.                 this jump is clearly incompatible with the
  103.                 one at the beginning of the repeat, such that
  104.                 we can be sure that there is no use backtracking
  105.                 out of repetitions already completed,
  106.                 then we finalize. */
  107. #define dummy_failure_jump 8  /* jump, and push a dummy failure point. */
  108.             /*  This failure point will be thrown away
  109.                 if an attempt is made to use it for a failure.
  110.                 A + construct makes this before the first repeat.  */
  111. #define anychar 9    /* matches any one character */
  112. #define charset 10    /* matches any one char belonging to specified set. */
  113.           /*  First following byte is # bitmap bytes.
  114.             Then come bytes for a bit-map saying which chars are in.
  115.             Bits in each byte are ordered low-bit-first.
  116.             A character is in the set if its bit is 1.
  117.             A character too large to have a bit in the map
  118.             is automatically not in the set */
  119. #define charset_not 11    /* similar but match any character that is NOT one of those specified */
  120. #define start_memory 12 /* starts remembering the text that is matched */
  121.           /*  and stores it in a memory register.
  122.             followed by one byte containing the register number.
  123.             Register numbers must be in the range 0 through NREGS. */
  124. #define stop_memory 13    /* stops remembering the text that is matched */
  125.           /*  and stores it in a memory register.
  126.             followed by one byte containing the register number.
  127.             Register numbers must be in the range 0 through NREGS. */
  128. #define duplicate 14    /* match a duplicate of something remembered. */
  129.           /*  Followed by one byte containing the index of the memory register. */
  130. #define before_dot 15    /* Succeeds if before dot */
  131. #define at_dot 16    /* Succeeds if at dot */
  132. #define after_dot 17    /* Succeeds if after dot */
  133. #define begbuf 18    /* Succeeds if at beginning of buffer */
  134. #define endbuf 19    /* Succeeds if at end of buffer */
  135. #define wordchar 20    /* Matches any word-constituent character */
  136. #define notwordchar 21    /* Matches any char that is not a word-constituent */
  137. #define wordbeg 22    /* Succeeds if at word beginning */
  138. #define wordend 23    /* Succeeds if at word end */
  139. #define wordbound 24    /* Succeeds if at a word boundary */
  140. #define notwordbound 25 /* Succeeds if not at a word boundary */
  141. #define syntaxspec 26    /* Matches any character whose syntax is specified. */
  142.             /* followed by a byte which contains a syntax code, Sword or such like */
  143. #define notsyntaxspec 27 /* Matches any character whose syntax differs from the specified. */
  144.  
  145.  
  146. #ifndef SIGN_EXTEND_CHAR
  147. #define SIGN_EXTEND_CHAR(x) (x)
  148. #endif
  149.  
  150. /* compile_pattern takes a regular-expression descriptor string in the user's format
  151.   and converts it into a buffer full of byte commands for matching.
  152.  
  153.   pattern   is the address of the pattern string
  154.   size        is the length of it.
  155.   bufp        is a  struct re_pattern_buffer *  which points to the info
  156.         on where to store the byte commands.
  157.         This structure contains a  char *  which points to the
  158.         actual space, which should have been obtained with malloc.
  159.         compile_pattern may use  realloc  to grow the buffer space.
  160.  
  161.   The number of bytes of commands can be found out by looking in
  162.   the  struct re_pattern_buffer     that bufp pointed to,
  163.   after compile_pattern returns.
  164. */
  165.  
  166. #define PATPUSH(ch) (*b++ = (char) (ch))
  167.  
  168. #define PATFETCH(c) \
  169.  {if (p == pend) goto end_of_pattern; \
  170.   c = * (unsigned char *) p++; \
  171.   if (translate) c = translate[c]; }
  172.  
  173. #define PATFETCH_RAW(c) \
  174.  {if (p == pend) goto end_of_pattern; \
  175.   c = * (unsigned char *) p++; }
  176.  
  177. #define PATUNFETCH p--
  178.  
  179. #define EXTEND_BUFFER \
  180.   { char *old_buffer = bufp->buffer; \
  181.     if (bufp->allocated == (1<<16)) goto too_big; \
  182.     bufp->allocated *= 2; \
  183.     if (bufp->allocated > (1<<16)) bufp->allocated = (1<<16); \
  184.     if (!(bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated))) \
  185.       goto memory_exhausted; \
  186.     c = bufp->buffer - old_buffer; \
  187.     b += c; \
  188.     if (fixup_jump) \
  189.       fixup_jump += c; \
  190.     if (laststart) \
  191.       laststart += c; \
  192.     begalt += c; \
  193.     if (pending_exact) \
  194.       pending_exact += c; \
  195.   }
  196.  
  197. static int store_jump (), insert_jump ();
  198.  
  199. char *
  200. re_compile_pattern (pattern, size, bufp)
  201.      char *pattern;
  202.      int size;
  203.      struct re_pattern_buffer *bufp;
  204. {
  205.   register char *b = bufp->buffer;
  206.   register char *p = pattern;
  207.   char *pend = pattern + size;
  208.   register unsigned c, c1;
  209.   char *p1;
  210.   unsigned char *translate = (unsigned char *) bufp->translate;
  211.  
  212.   /* address of the count-byte of the most recently inserted "exactn" command.
  213.     This makes it possible to tell whether a new exact-match character
  214.     can be added to that command or requires a new "exactn" command. */
  215.  
  216.   char *pending_exact = 0;
  217.  
  218.   /* address of the place where a forward-jump should go
  219.     to the end of the containing expression.
  220.     Each alternative of an "or", except the last, ends with a forward-jump
  221.     of this sort. */
  222.  
  223.   char *fixup_jump = 0;
  224.  
  225.   /* address of start of the most recently finished expression.
  226.     This tells postfix * where to find the start of its operand. */
  227.  
  228.   char *laststart = 0;
  229.  
  230.   /* In processing a repeat, 1 means zero matches is allowed */
  231.  
  232.   char zero_times_ok;
  233.  
  234.   /* In processing a repeat, 1 means many matches is allowed */
  235.  
  236.   char many_times_ok;
  237.  
  238.   /* addr